package com.lft.ten_commonly_used_algorithms07.kruskal;

import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 */
public class KruskalAlgorithmDemo {
	public static void main(String[] args) {
		char[] vertexes = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		int[][] matrix = {
				/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
				/*A*/{0, 12, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 16, 14},
				/*B*/{12, 0, 10, Integer.MAX_VALUE, Integer.MAX_VALUE, 7, Integer.MAX_VALUE},
				/*C*/{Integer.MAX_VALUE, 10, 0, 3, 5, 6, Integer.MAX_VALUE},
				/*D*/{Integer.MAX_VALUE, Integer.MAX_VALUE, 3, 0, 4, Integer.MAX_VALUE, Integer.MAX_VALUE},
				/*E*/{Integer.MAX_VALUE, Integer.MAX_VALUE, 5, 4, 0, 2, 8},
				/*F*/{16, 7, 6, Integer.MAX_VALUE, 2, 0, 9},
				/*G*/{14, Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 8, 9, 0}
		};
		KruskalAlgorithm kruskalAlgorithm = new KruskalAlgorithm(vertexes, matrix);
		kruskalAlgorithm.displayGraph();
		// 边数组未排序
		EdgeData[] edges = kruskalAlgorithm.getEdges();
		System.out.println("排序前：");
		System.out.println(Arrays.toString(edges));
		// 排序后为
		kruskalAlgorithm.sortEdges(edges);
		System.out.println("排序后：");
		System.out.println(Arrays.toString(edges));
		// 使用克鲁斯卡尔算法
		kruskalAlgorithm.kruskal();
		
	}
	
}

class KruskalAlgorithm {
	/**
	 * 顶点数组
	 */
	private char[] vertexes;
	/**
	 * 边的数量
	 */
	private int numOfEdges;
	
	/**
	 * 邻接矩阵
	 */
	private int[][] edgesMatrix;
	/**
	 * 最大值 表示两个顶点不联通。
	 */
	private static final int MAX = Integer.MAX_VALUE;
	
	public KruskalAlgorithm(char[] vertexes, int[][] edgesMatrix) {
		// 顶点数量
		int numOfVertexes = vertexes.length;
		// 初始化顶点数组,防止修改原数据。
		this.vertexes = new char[numOfVertexes];
		for (int i = 0; i < vertexes.length; i++) {
			this.vertexes[i] = vertexes[i];
		}
		this.edgesMatrix = new int[numOfVertexes][numOfVertexes];
		// 初始化 邻接矩阵，防止修改原数据。
		for (int i = 0; i < edgesMatrix.length; i++) {
			for (int j = 0; j < edgesMatrix[i].length; j++) {
				// 复制边信息
				this.edgesMatrix[i][j] = edgesMatrix[i][j];
			}
		}
		// 统计边数量
		for (int i = 0; i < edgesMatrix.length; i++) {
			// 从其后面一个开始。无向图。不重复处理边。
			for (int j = i + 1; j < edgesMatrix[i].length; j++) {
				if (this.edgesMatrix[i][j] != MAX && this.edgesMatrix[i][j] != 0) {
					this.numOfEdges++;
				}
			}
		}
	}
	
	/**
	 * 对边时行排序 ，冒泡排序
	 * @param edgeDataArray
	 */
	public void sortEdges(EdgeData[] edges) {
		// 遍历数组所有元素。
		for (int i = 0; i < edges.length - 1; i++) {
			// 遍历 所有元素 - 已经遍历元素 次数
			for (int j = 0; j < edges.length - 1 - i; j++) {
				// 找到最大的，放在最后。
				if (edges[j].weight > edges[j + 1].weight) {
					EdgeData temp = edges[j];
					edges[j] = edges[j + 1];
					edges[j + 1] = temp;
				}
			}
		}
	}
	
	/**
	 * 根据提供的顶点元素返回顶点所在顶点数组中的索引。
	 * @param vertex 顶点
	 * @return 顶点所在数组的索引。找不到返回 -1
	 */
	public int getVertexIndex(char vertex) {
		for (int i = 0; i < vertexes.length; i++) {
			// 找到
			if (vertexes[i] == vertex) {
				return i;
			}
		}
		return -1;
	}
	
	/**
	 * 获取图中的边，放到 EdgeData 数组中,后面需要遍历该数组
	 * 通过 matrix 邻接矩阵来获取。
	 * EdgeData[] 形式 [['A','B',12],['E','F',8],...]
	 * @return EdgeData[]
	 */
	public EdgeData[] getEdges() {
		EdgeData[] results = new EdgeData[numOfEdges];
		// 指向上面数组的索引
		int tempIndex = 0;
		for (int i = 0; i < vertexes.length; i++) {
			for (int j = i + 1; j < vertexes.length; j++) {
				if (edgesMatrix[i][j] != 0 && edgesMatrix[i][j] != MAX) {
					results[tempIndex++] = new EdgeData(vertexes[i], vertexes[j], edgesMatrix[i][j]);
				}
			}
		}
		return results;
	}
	
	/**
	 * 获取索引为 i 的顶点的最大终点，用于后面判断两个顶点的终点是否相同。
	 * @param endPoints 记录各个顶点对应的终点是哪个的终点集合。是在遍历过程中逐步形成的。
	 * @param i         当前顶点索引
	 * @return 返回的就是下标为 i 的这个顶点对应的终点的索引。
	 */
	public int getMaxEndPoint(int[] endPoints, int i) {
		while (endPoints[i] != 0) {
			i = endPoints[i];
		}
		return i;
	}
	
	public void kruskal() {
		// 表示最后结果数组的索引
		int index = 0;
		// 用于保存已经最小生成树中的每个顶点在最小生成树中的终点。
		int[] endPoints = new int[numOfEdges];
		// 创建结果集。
		EdgeData[] results = new EdgeData[numOfEdges];
		
		// 获取图中所有的边的集合。
		EdgeData[] edges = getEdges();
		// System.out.println(Arrays.toString(edges));
		// System.out.println(edges.length);
		
		// 将原始边的数组按边的权重从小到大排序
		sortEdges(edges);
		
		// 遍历 edges 数组，判断要添加的边是否形成了回路。如果没有就加入 results 数组。否则遍历下一个。
		for (int i = 0; i < numOfEdges; i++) {
			// 获取第 i 条边的开始顶点索引
			int startVertexIndex = getVertexIndex(edges[i].start);
			// 获取第 i 条边的结束顶点索引
			int endVertexIndex = getVertexIndex(edges[i].end);
			
			// 获取 startVertexIndex 顶点在最小生成树结果集中的最大终点的索引
			int startMaxEndPointIndex = getMaxEndPoint(endPoints, startVertexIndex);
			// 获取 startVertexIndex 顶点在最小生成树结果集中的最大终点的索引
			int endMaxEndPointIndex = getMaxEndPoint(endPoints, endVertexIndex);
			
			// 没有构成回路
			if (startMaxEndPointIndex != endMaxEndPointIndex) {
				// 设置 startMaxEndPointIndex 顶点在已有的最小生成树集合中的终点索引为 endMaxEndPointIndex
				endPoints[startMaxEndPointIndex] = endMaxEndPointIndex;
				// 将当前边加入到 最小生成树数组
				results[index++] = edges[i];
			}
		}
		
		// 统计并打印“最小生成树”。输出results
		// System.out.println("最小生成树：" + Arrays.toString(results));
		System.out.println("最小生成树：");
		for (int i = 0; i < results.length; i++) {
			if (results[i] != null) {
				// System.out.println("边 < " + results[i].start + "," + results[i].end + "> 权值：" + results[i].weight);
				System.out.print(results[i]);
			}
		}
	}
	
	/**
	 * 打印邻接矩阵
	 */
	public void displayGraph() {
		System.out.println("邻接矩阵：");
		for (int i = 0; i < vertexes.length; i++) {
			for (int j = 0; j < vertexes.length; j++) {
				System.out.printf("%12d", edgesMatrix[i][j]);
			}
			System.out.println();
		}
	}
	
}

/**
 * 定义一个表示边的类
 */
class EdgeData {
	/**
	 * 边的起点
	 */
	char start;
	/**
	 * 边的终点
	 */
	char end;
	/**
	 * 边的权重
	 */
	int weight;
	
	public EdgeData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	
	@Override
	public String toString() {
		return "边 <" + start + "," + end + "> 的权值：" + weight + "\n";
	}
}
